package _str

import org.junit.Assert
import org.junit.Test

/*
  https://leetcode.cn/problems/reverse-string/description/
  https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
  
  344. 反转字符串
  编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
  不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

  示例 1：

    输入：s = ['h','e','l','l','o']
    输出：['o','l','l','e','h']

   示例 2：

    输入：s = ['H','a','n','n','a','h']
    输出：['h','a','n','n','a','H']
 */
class leetcode_344 {
    @Test
    fun test_1() {
        val array = charArrayOf('h', 'e', 'l', 'l', 'o')
        reverseString(array)
        val expect = charArrayOf('o', 'l', 'l', 'e', 'h')
        Assert.assertEquals(expect.contentToString(), array.contentToString())
    }

    @Test
    fun test_2() {
        val array = charArrayOf('H', 'a', 'n', 'n', 'a', 'h')
        reverseString(array)
        val expect = charArrayOf('h', 'a', 'n', 'n', 'a', 'H')
        Assert.assertEquals(expect.contentToString(), array.contentToString())
    }

    fun reverseString(s: CharArray): Unit {
        /*
        题型：字符串的双指针法

        left  = 0, right = end index
        left < right, swipe data,  left++,right--

        时间复杂度：O(N)
        空间复杂度：O(1)
         */
        //
        // S - 1
        if (s.isEmpty()) {
            return
        }
        var left: Int = 0
        var right: Int = s.size - 1
        var temp: Char
        while (left < right) {
            // 交换
            temp = s[left]
            s[left] = s[right]
            s[right] = temp

            left++
            right--
        }
    }
}